# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        def merge(head1, head2):
            newHead = ListNode(None)
            cur = newHead
            while head1 and head2:
                if head1.val<head2.val:
                    cur.next = head1
                    head1 = head1.next
                    cur = cur.next
                    cur.next = None
                else:
                    cur.next = head2
                    head2 = head2.next
                    cur = cur.next
                    cur.next = None
            while head1:
                cur.next = head1
                head1 = head1.next
                cur = cur.next
                cur.next = None
            while head2:
                cur.next = head2
                head2 = head2.next
                cur = cur.next
                cur.next = None
            return newHead.next
        return merge(l1, l2)